package problems.daily;

import java.util.Arrays;

/**
 * 1235. 规划兼职工作
 * <p>https://leetcode.cn/problems/maximum-profit-in-job-scheduling/</p>
 *
 * @author habitplus
 * @since 10:46, 2022/10/22
 */
public class DT1235 {
    public int jobScheduling1(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] arr = new int[n][3];

        for (int i = 0; i < n; ++i) {
            arr[i][0] = startTime[i];
            arr[i][1] = endTime[i];
            arr[i][2] = profit[i];
        }

        // 按结束时间升序排序
        Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);

        // dp[i] 表示前 i 个兼职所能获得的最大报酬
        // dp[i] = max(dp[i-1], dp[k] + profit[i-1])
        // 其中，i>0
        // dp[k]表示前i个兼职中结束时间<=第i-1个任务的最大利润
        int[] dp = new int[n + 1];

        dp[0] = 0;
        int k;

        for (int i = 1; i <= n; ++i) {
            k = findClosest(arr, 0, i - 1, arr[i - 1][0]);
            dp[i] = Math.max(dp[i - 1], dp[k] + arr[i - 1][2]);
        }

        return dp[n];
    }

    /**
     * 找到最靠近 <= target 的最大下标
     */
    private int findClosest(int[][] arr, int left, int right, int target) {
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (arr[mid][1] > target) right = mid;
            else left = mid + 1;
        }
        return left;
    }


    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] arr = new int[n][3];

        for (int i = 0; i < n; ++i) {
            arr[i][0] = startTime[i];
            arr[i][1] = endTime[i];
            arr[i][2] = profit[i];
        }

        // 按结束时间升序排序
        Arrays.sort(arr, (o1, o2) -> o1[1] - o2[1]);

        int[] dp = new int[n + 1];
        int k;

        for (int i = 1; i <= n; ++i) {
            k = i - 1;
            while (k >= 0 && arr[k][1] > arr[i-1][0]) --k;
            k = Math.max(0, k);

//            k = 0;
//            // 向前寻找“最近的”“已完成的"兼职工作
//            for (int j = i - 1; j >= 0; --j) {
//                if (arr[j][1] <= arr[i - 1][0]) {
//                    k = j + 1;
//                    break;
//                }
//            }
            dp[i] = Math.max(dp[i - 1], dp[k] + arr[i - 1][2]);
        }

        return dp[n];
    }
}
